// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func sortedArrayToBST(array []int) *TreeNode {
	if len(array) == 0 {
		return nil
	}

	// 找到数组的中间元素
	mid := len(array) / 2

	// 新建一个以中间元素为根的TreeNode
	root := &TreeNode{Val: array[mid]}

	//递归构造左右子树
	root.Left = sortedArrayToBST(array[:mid])
	root.Right = sortedArrayToBST(array[mid+1:])

	return root
}

func main() {
	array := []int{1, 2, 3, 4, 5, 6, 7, 8}
	root := sortedArrayToBST(array)
	fmt.Println(root.Val)
}

//$ go run balancedBinaryTree.go
//5
